#pragma once

#include "Container_t.h"

/* A template class (T - template parameter) class that represents a node of a link list,
   where its data is a pointer to T.
*/
template <class T> class node
{

private:
	
	T* data;
	node* prev;
	node* next;

public:

	//gets data; prev. and next. nodes.
	node(T* dat, node* prv, node* nxt) : data(dat), prev(prv), next(nxt) {
 
	}

	~node() {

	}

	T* getData() const {

		return data;
	}

	void setData(T* dat) {

		data = dat;
	}

	node<T>* getPrev() const {

		return prev;
	}

	void setPrev(node<T>* prv) {

		prev = prv;
	}

	node<T>* getNext() const {

		return next;
	}

	void setNext(node<T>* nxt) {

		next = nxt;
	}
};


/* A template class (T - template parameter),
   that represents a doubly linked list container (extends class container), 
   which can hold pointers to T.
   Allows various operations on doubly linked list container, such as:
   insert(), remove(), find() and more.
*/
template <class T> class Dlist_t : public Container_t<T>
{

private:

	node<T>* head;
	node<T>* tail;
	node<T>* currNode;

public:

	Dlist_t() {

		head = 0;
		tail = 0;
		currNode = 0;
	}

	//copy CTOR.
	Dlist_t(const Dlist_t<T>& lst) : Container_t(lst) {

		T* curr = lst.Reset();  //getting head's element.

		while (curr != 0) {

			insert(curr);

			curr = lst.Next();
		}

		Reset();
	}


	virtual ~Dlist_t() {

		removeAll();
	}

	//assignment operator for dlist.
	virtual Dlist_t<T>& operator=(Dlist_t<T>& lst) {

		if (this != &lst) {  //to forbid a=a.
			
			removeAll();

			Container_t<T>::operator=(lst);  //calling operator= of base class.

			T* curr = lst.Reset();  //getting head's element.

			while (curr != 0) {

				insert(curr);

				curr = lst.Next();
			}

			Reset();
		}

		return *this;
	}

	/* seacrhes for a value in dlist, 
	   and returns pointer to it, if found (null ptr. if not). */
	virtual T* find(const T& value) {

		T* curr = Reset();  //getting head's element.

		while (curr != 0) {

			if (*curr == value) {
				return curr;
			}

			curr = Next();
		}
	
		return 0;  //not found - null ptr.
	}

	//inserts element at end of dlist.
	virtual void insert(T* elem) {

		node<T>* toAdd = 0;

		if (tail == 0) {  //head is also NULL.
			toAdd = new node<T>(elem, 0, 0);
			head = toAdd; 
			tail = toAdd;
		} else {
			toAdd = new node<T>(elem, tail, 0);
			tail->setNext(toAdd);
			tail = toAdd;
		}

		numOfElements++;
	}


	//appends element after given index in dlist.
	virtual void append(T* elem, int index) {

		if (!indexInBounds(index)) {
			throw("Index out of bounds - dlist append operation.");
		}

		if (count() == 0) {
			throw("Append to an empty dlist is illegal.");
		}

		int i = 0;
		node<T>* curr = head;

		while (i < index) {

			curr = curr->getNext();
			i++;
		}

		node<T>* nextToCurr = curr->getNext();
		node<T>* toAdd = new node<T>(elem, curr, nextToCurr);
		curr->setNext(toAdd);

		if (nextToCurr == 0) {
			tail = toAdd;
		} else {
			nextToCurr->setPrev(toAdd);
		}

		numOfElements++;
	}

	//prepends element before given index in dlist.
	virtual void prepend(T* elem, int index) {

		if (!indexInBounds(index)) {
			throw("Index out of bounds - dlist prepend operation.");
		}

		if (count() == 0) {
			throw("Prepend to an empty dlist is illegal.");
		}

		int i = 0;
		node<T>* curr = head;

		while (i < index) {

			curr = curr->getNext();
			i++;
		}

		node<T>* prevToCurr = curr->getPrev();
		node<T>* toAdd = new node<T>(elem, prevToCurr, curr);
		curr->setPrev(toAdd);

		if (prevToCurr == 0) {
			head = toAdd;
		} else {
			prevToCurr->setNext(toAdd);
		}

		numOfElements++;
	}

	/* removes element from dlist, given its value (if found).
	   returns pointer to it, if found (null ptr. if not). */
	virtual T* remove(const T& value) {

		T* curr = Reset();  //getting head's element.

		while (curr != 0) {

			if (*curr == value) {
				
				removeNode(currNode);

				return curr;
			}

			curr = Next();
		}
	
		return 0;  //not found - null ptr.
	}

	/* removes element from dlist, given its value (if found).
	   afterwards, deletes it. */
	virtual void removeAndDelete(const T& value) {

		delete remove(value);  //if remove(value) == 0, delete does nothing.
	}
	
	//removes all elements from dlist.
	virtual void removeAll() {

		node<T>* curr = head;
		node<T>* tmpNext = 0;

		while (curr != 0) {  //frees linked list.

			tmpNext = curr->getNext();
			delete curr;
			curr = tmpNext;
		}

		Container_t<T>::removeAll();  //sets numOfElements to 0.
	}

	//removes and deletes all elements from dlist.
	virtual void removeAndDeleteAll() {

		node<T>* curr = head;
		node<T>* tmpNext = 0;

		while (curr != 0) {  //frees linked list and deletes elements.

			tmpNext = curr->getNext();
			delete curr->getData();
			delete curr;
			curr = tmpNext;
		}

		Container_t<T>::removeAndDeleteAll();  //sets numOfElements to 0.
	}

	//returns next element in dlist.
	T* Next() {

		if (currNode == tail) {
			return 0;
		}
	
		currNode = currNode->getNext();
		return currNode->getData();
	}
	
	//returns previous element in dlist.
	T* Prev() {

		if (currNode == head) {
			return 0;
		}
	
		currNode = currNode->getPrev();
		return currNode->getData();
	}

	/* puts internal pointer to curr. node, to point to dlist head,
	   and returns the element of head. */
	T* Reset() {

		currNode = head;
		
		if (currNode == 0) {
			return 0;
		} else {
			return currNode->getData();
		}
	}

private:

	//removes given node from linked list.
	void removeNode(node<T>* nd) {

		node<T>* prv = nd->getPrev();
		node<T>* nxt = nd->getNext();

		if (prv != 0)  {  //not head.
			prv->setNext(nxt);
		} else {  //head.
			head = nxt;
		}

		if (nxt != 0)  {  //not tail.
			nxt->setPrev(prv);
		} else {  //tail.
			tail = prv;
		}

		delete nd;

		numOfElements--;
	}

};

